package BinarySearch;

class BinarySearchAlternative {
  // 最坏情况 O(log(n))
  // 最好情况 O(1)
  int fn(int arr[], int target) {
    int i = 0, j = arr.length; // 第一处
    while (i < j) { // 第二处
      int mid = (i + j) >>> 1;
      if (arr[mid] < target) { // target在最右侧执行 L 次
        i = mid + 1;
      } else if (target < arr[mid]) { // target在最左侧执行 2 * L 次
        j = mid; // 第三处
      } else {
        return mid;
      }
    }
    return -1;
  }
}
